package com.yuren.codecrushlearn.Q5200;

/**
 * Created with Intellij IDEA.
 * Description:
 * 基于链表法实现HashMap
 *
 * @author 10204
 * @date 2025-04-24 00:18
 */
public class Q5214 {
    int capacity;
    Node[] nodes;

    public Q5214() {
        capacity = 1024;
        nodes = new Node[capacity];
    }

    public void put(int key, int value) {
        int idx = hash(key) & (capacity - 1);
        Node now = nodes[idx], tmp = now;
        if (tmp != null) {
            Node prev = null;
            while (tmp != null) {
                if (tmp.key == key) {
                    tmp.value = value;
                    return;
                }
                prev = tmp;
                tmp = tmp.next;
            }
            tmp = prev;
        }

        Node node = new Node(key, value);
        if (tmp != null) {
            tmp.next = node;
        } else {
            nodes[idx] = node;
        }
    }

    public int get(int key) {
        int idx = hash(key) & (capacity - 1);
        Node now = nodes[idx];

        if (now != null) {
            if (now.key == key) {
                return now.value;
            } else {
                while (now != null) {
                    if (now.key == key) {
                        return now.value;
                    }
                    now = now.next;
                }
            }
        }

        return -1;
    }

    public void remove(int key) {
        int idx = hash(key) & (capacity - 1);
        Node now = nodes[idx];

        if (now != null) {
            Node prev = null;
            while (now != null) {
                if (now.key == key) {
                    if (prev != null) {
                        prev.next = now.next;
                    }else {
                        nodes[idx] = now.next;
                    }
                    now.next = null;
                    return;
                }
                prev = now;
                now = now.next;
            }
        }
    }

    private int hash(int key) {
        int hash = Integer.hashCode(key);
        hash ^= (hash >>> 16);
        return hash;
    }

    static class Node{
        int key, value;
        Node next;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
}

